// n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

// 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

// 每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。


/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
    // 初始化棋盘
    let board = new Array(n);
    for (let i = 0; i <= board.length - 1; i++) {
        board[i] = new Array(n)
        for (let j = 0; j <= board[i].length - 1; j++) {
            board[i][j] = '.';
        }
    };
    // 初始化数组集合
    let res = [];
    // 定义剪枝函数
    let isValid = function (board, row, col) {
        // 检查列
        for (let b = row - 1; b >= 0; b--) {
            if (board[b][col] === 'Q') return false
        }
        // 检查左斜线
        for (let ar = row - 1, ac = col - 1; ar >= 0 && ac >= 0; ar-- , ac--) {
            if (board[ar][ac] === 'Q') return false
        }
        // 检查右斜线
        for (let cr = row - 1, cc = col + 1; cr >= 0 && cc <= n - 1; cr-- , cc++) {
            if (board[cr][cc] === 'Q') return false
        }
        return true;
    }
    // 定义及执行回溯
    let backTrack = function (board, row) {
        // 检查中止条件：最后一行选择完成，row = n（rowMax = n-1）
        if (row == n) {
            // 保存此时board的shortcut
            // 需要深拷贝，否则board移植被改变
            let copy = board.map(rowItem => {
                return rowItem.join('');
            })
            res.push(copy);
            return;
        }
        // 遍历决策树,一行的每一个位置均有可能放置
        for (let col = 0; col <= board[row].length - 1; col++) {
            // 决策树剪枝:不符合条件，跳过该位置的选择
            if (!isValid(board, row, col)) continue;
            // 做选择，一行仅放一个，放完就下一层决策
            board[row][col] = 'Q';
            // 下一层决策
            backTrack(board, row + 1);
            //撤回
            board[row][col] = '.';
        }
    };
    backTrack(board, 0);
    return res;
};